//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n, 1);
//        int ret = 0;
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                if (nums[j] < nums[i])
//                {
//                    dp[i] = max(dp[j] + 1, dp[i]);
//                }
//            }
//            ret = max(dp[i], ret);
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<vector<string>> ret;
//    vector<string> path;
//    int n;
//    vector<vector<string>> partition(string s) {
//        n = s.size();
//        dfs(s, 0);
//        return ret;
//    }
//    void dfs(string s, int start)
//    {
//        if (start == n)
//        {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = start; i < n; i++)
//        {
//            string str = s.substr(start, i - start + 1);
//            if (isbackstr(str))
//            {
//                path.push_back(str);
//                dfs(s, i + 1);
//                path.pop_back();
//            }
//        }
//    }
//    bool isbackstr(string s)
//    {
//        if (s.size() == 1) return true;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] != s[s.size() - i - 1]) return false;
//        }
//        return true;
//    }
//};

